1. Technical Field
The invention relates to cryptography. More particularly, the invention relates to a method and apparatus for offline cryptographic key establishment.
2. Description of the Prior Art
The Diffie-Hellman key agreement protocol (also called exponential key agreement) was developed by Diffie and Hellman [W. Diffie and M. E. Hellman, New directions in cryptography, IEEE Transactions on Information Theory 22 (1976), 644-654] in 1976 and published in the paper “New Directions in Cryptography.” The protocol allows two users to exchange a secret key over an insecure medium without having previously exchanged secrets. The protocol has two system parameters p and g. They are both public and may be used by all the users in a system. Parameter p is a prime number and parameter g (usually called a generator) is an integer less than p, with the following property:                for every number n between 1 and p−1 inclusive, there is a power k of g such that n=gk mod p.        
Suppose Alice and Bob want to agree on a shared secret key using the Diffie-Hellman key agreement protocol. They proceed as follows:
First, Alice generates a random private value a and Bob generates a random private value b. Both, a and b are drawn from the set of integers. Then they derive their public values using both parameters p and g and their private values a and b. Alice's public value is ga mod p and Bob's public value is gb mod p. They then exchange their public values. Finally, Alice computes gab=(gb)a mod p, and Bob computes gba=(ga)b mod p. Because gab=gba=k, Alice and Bob now have a shared secret key k.
The protocol depends on the discrete logarithm problem for its security. It assumes that it is computationally infeasible to calculate the shared secret key k=gab mod p given the two public values ga mod p and gb mod p when the prime p is sufficiently large. Maurer [U. Maurer, Towards the equivalence of breaking the Diffie-Hellman protocol and computing discrete logarithms, Advances in Cryptology—Crypto '94, Springer-Verlag (1994), 271-281] has shown that breaking the Diffie-Hellman protocol is equivalent to computing discrete logarithms under certain assumptions.
The Diffie-Hellman key exchange is vulnerable to a man-in-the-middle attack. In this attack, an opponent Carol intercepts Alice's public value and sends her own public value to Bob. When Bob transmits his public value, Carol substitutes it with her own and sends it to Alice. Carol and Alice thus agree on one shared key and Carol and Bob agree on another shared key. After this exchange, Carol simply decrypts any messages sent out by Alice or Bob, and then reads and possibly modifies them before re-encrypting with the appropriate key and transmitting them to the other party. This vulnerability is present because Diffie-Hellman key exchange does not authenticate the participants.
Known solutions include the use of digital signatures and other protocol variants. The authenticated Diffie-Hellman key agreement protocol, or Station-to-Station (STS) protocol, was developed by Diffie, van Oorschot, and Wiener in 1992 [W. Diffie, P. C. van Oorschot, and M. J. Wiener, Authentication and authenticated key exchanges, Designs, Codes and Cryptography 2 (1992), 107-125] to defeat the man-in-the-middle attack on the Diffie-Hellman key agreement protocol. The immunity is achieved by allowing the two parties to authenticate themselves to each other by the use of digital signatures and public-key certificates.
Roughly speaking, the basic idea is as follows:
Prior to execution of the protocol, the two parties Alice and Bob each obtain a public/private key pair and a certificate for the public key. During the protocol, Alice computes a signature on certain messages, covering the public value ga mod p. Bob proceeds in a similar way. Even though Carol is still able to intercept messages between Alice and Bob, she cannot forge signatures without Alice's private key and Bob's private key. Hence, the enhanced protocol defeats the man-in-the-middle attack. In this scenario, Alice and Bob know each other and have no need to authenticate each other's identity.
Authentication is any process through which one proves and verifies certain information. Sometimes one may want to verify the origin of a document, the identity of the sender, the time and date a document was sent and/or signed, the identity of a computer or user, and so on.
A digital signature is a cryptographic means through which many of these may be verified. The digital signature of a document is a piece of information based on both the document and the signer's private key. It is typically created through the use of a hash function and a private signing function (encrypting with the signer's private key), but there are other methods.
Every day, people sign their names to letters, credit card receipts, and other documents, demonstrating they are in agreement with the contents. That is, they authenticate that they are in fact the sender or originator of the item. This allows others to verify that a particular message did indeed originate from the signer. However, this is not foolproof because people can lift signatures off one document and place them on another, thereby creating fraudulent documents. Written signatures are also vulnerable to forgery because it is possible to reproduce a signature on other documents as well as to alter documents after they have been signed.
Digital signatures and hand-written signatures both rely on the fact that it is very hard to find two people with the same signature. People use public-key cryptography to compute digital signatures by associating something unique with each person. When public-key cryptography is used to encrypt a message, the sender encrypts the message with the public key of the intended recipient. When public-key cryptography is used to calculate a digital signature, the sender encrypts the digital fingerprint of the document with his own private key. Anyone with access to the public key of the signer may verify the signature.
Suppose Alice wants to send a signed document or message to Bob. The first step is generally to apply a hash function to the message, creating what is called a message digest. The message digest is usually considerably shorter than the original message. In fact, the job of the hash function is to take a message of arbitrary length and shrink it down to a fixed length. To create a digital signature, one usually signs (encrypts) the message digest as opposed to the message itself. This saves a considerable amount of time, though it does create a slight insecurity. Alice sends Bob the encrypted message digest and the message, which she may or may not encrypt. For Bob to authenticate the signature he must apply the same hash function as Alice to the message she sent him, decrypt the encrypted message digest using Alice's public key and compare the two. If the two are the same he has successfully authenticated the signature. If the two do not match there are a few possible explanations. Either someone is trying to impersonate Alice, the message itself has been altered since Alice signed it, or an error occurred during transmission
Certificates are digital documents attesting to the binding of a public key to an individual or other entity. They allow verification of the claim that a specific public key does in fact belong to a specific individual. Certificates help prevent someone from using a phony key to impersonate someone else. In some cases it may be necessary to create a chain of certificates, each one certifying the previous one until the parties involved are confident in the identity in question.
In their simplest form, certificates contain a public key and a name. As commonly used, a certificate also contains an expiration date, the name of the certifying authority that issued the certificate, a serial number, and perhaps other information. Most importantly, it contains the digital signature of the certificate issuer. The most widely accepted format for certificates is defined by the ITU-T X.509 international standard; thus, certificates can be read or written by any application complying with X.509.
While the use of asymmetrical encryption schemes, such as Diffie-Hellman, in concert with various authentication schemes, such as the use of digital signatures and certificates is known, it is not currently known how to share keys between networked devices that do not communicate directly with one another. For example, network storage devices may exchange encrypted information on the basis of asymmetrical cryptographic techniques, such as the use of Diffie-Hellman. However, such devices may be initially unknown to each other and, therefore, lack sufficient trust to exchange such information over an insecure medium. It would be advantageous to provide an authentication scheme that allowed such networked devices to establish trust in connection with the exchange of keys pursuant to an asymmetrical cryptographic technique, such as Diffie-Hellman.